package com.cyy.test_t_3_;


import com.cyy.test.util.TreeNode;

/**
 * 剑指Offer 面试题39_2 
 * 平衡二叉树
 * 题目描述：
 * 输入一棵二叉树，判断该二叉树是否是平衡二叉树。
 */
public class t_39_2 {
	 
	public boolean IsBalanced(TreeNode root) {
	    if(root == null)
	    	return true;
	    
	    int nLeft = TreeDepth(root.left);
	    int nRight = TreeDepth(root.right);
	    int diff = (nLeft > nRight) ? (nLeft - nRight) : (nRight - nLeft);
	    
	    if(diff > 1) return false;
	    return IsBalanced(root.left) && IsBalanced(root.right);
	}
	
	public static int TreeDepth(TreeNode root) {
        if(root == null)
            return 0;
        int nLeft = TreeDepth(root.left);
        int nRight = TreeDepth(root.right);
        
        return (nLeft > nRight) ? (nLeft + 1) : (nRight + 1);
 }
}
